<!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"><meta name="description" content="位图排序"><meta name="keywords" content="算法艺术"><meta name="author" content="LiYang"><meta name="copyright" content="LiYang"><title>位图排序 | 一条鲤鱼</title><link rel="shortcut icon" href="/melody-favicon.ico"><link rel="stylesheet" href="/css/index.css?version=1.9.0"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome@latest/css/font-awesome.min.css?version=1.9.0"><meta name="format-detection" content="telephone=no"><meta http-equiv="x-dns-prefetch-control" content="on"><link rel="dns-prefetch" href="https://cdn.jsdelivr.net"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><script>var GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: undefined,
  copy: {
    success: 'Copy successfully',
    error: 'Copy error',
    noSupport: 'The browser does not support'
  },
  hexoVersion: '5.4.0'
} </script><meta name="generator" content="Hexo 5.4.0"><link rel="alternate" href="/atom.xml" title="一条鲤鱼" type="application/atom+xml">
</head><body><i class="fa fa-arrow-right" id="toggle-sidebar" aria-hidden="true"></i><div id="sidebar" data-display="true"><div class="toggle-sidebar-info text-center"><span data-toggle="Toggle article">Toggle site</span><hr></div><div class="sidebar-toc"><div class="sidebar-toc__title">Catalog</div><div class="sidebar-toc__progress"><span class="progress-notice">You've read</span><span class="progress-num">0</span><span class="progress-percentage">%</span><div class="sidebar-toc__progress-bar"></div></div><div class="sidebar-toc__content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BD%8D%E5%9B%BE%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95"><span class="toc-number">1.</span> <span class="toc-text">位图排序算法</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%8B%E7%BB%8D"><span class="toc-number">1.1.</span> <span class="toc-text">介绍</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BE%E4%B8%AA%E4%BE%8B%E5%AD%90"><span class="toc-number">1.1.1.</span> <span class="toc-text">举个例子</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%EF%BC%88C-%EF%BC%89"><span class="toc-number">1.2.</span> <span class="toc-text">算法实现（C++）</span></a></li></ol></li></ol></div></div><div class="author-info hide"><div class="author-info__avatar text-center"><img src="/img/avatar.png"></div><div class="author-info__name text-center">LiYang</div><div class="author-info__description text-center"></div><hr><div class="author-info-articles"><a class="author-info-articles__archives article-meta" href="/archives"><span class="pull-left">Articles</span><span class="pull-right">13</span></a><a class="author-info-articles__tags article-meta" href="/tags"><span class="pull-left">Tags</span><span class="pull-right">6</span></a><a class="author-info-articles__categories article-meta" href="/categories"><span class="pull-left">Categories</span><span class="pull-right">7</span></a></div></div></div><div id="content-outer"><div class="no-bg" id="top-container"><div id="page-header"><span class="pull-left"> <a id="site-name" href="/">一条鲤鱼</a></span><i class="fa fa-bars toggle-menu pull-right" aria-hidden="true"></i><span class="pull-right menus">   <a class="site-page" href="/">Home</a><a class="site-page" href="/archives">Archives</a><a class="site-page" href="/tags">Tags</a><a class="site-page" href="/categories">Categories</a></span><span class="pull-right"></span></div><div id="post-info"><div id="post-title">位图排序</div><div id="post-meta"><time class="post-meta__date"><i class="fa fa-calendar" aria-hidden="true"></i> 2021-12-02</time><span class="post-meta__separator">|</span><i class="fa fa-inbox post-meta__icon" aria-hidden="true"></i><a class="post-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></div></div></div><div class="layout" id="content-inner"><article id="post"><div class="article-container" id="post-content"><h1 id="位图排序算法"><a href="#位图排序算法" class="headerlink" title="位图排序算法"></a>位图排序算法</h1><p><strong>位图法：bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。</strong></p>
<h2 id="介绍"><a href="#介绍" class="headerlink" title="介绍"></a>介绍</h2><p>​        位图排序是一种<strong>效率极高(复杂度可达O(n))并且很节省空间</strong>的一种排序方法，但是这种排序方法对输入的数据是有比较严格的要求(<strong>数据不能重复，大致知道数据的范围</strong>)。位图排序即利用位图或者位向量来表示集合。可以说算法中用到位操作的很多，因为速度快，空间小，比如还有<strong>bitmask dp</strong>（例题：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes/">847. 访问所有节点的最短路径</a>。）</p>
<h3 id="举个例子"><a href="#举个例子" class="headerlink" title="举个例子"></a>举个例子</h3><p>对unsigned没有重复的数字进行排序，假设我们要对0-7内的5个元素(4,7,2,5,3)排序。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，如下图：</p>
<p><img src="/2021/12/02/%E4%BD%8D%E5%9B%BE%E6%8E%92%E5%BA%8F/8394323_1303655564K05X.jpg" alt="8394323_1303655564K05X"></p>
<p>然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作：p+(i/8)|(0x01&lt;&lt;(i%8)）当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为一（如下图）：</p>
<p><img src="/2021/12/02/%E4%BD%8D%E5%9B%BE%E6%8E%92%E5%BA%8F/8394323_1303655564rRn3.jpg" alt="8394323_1303655564rRn3"></p>
<p>接着再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：</p>
<p><img src="/2021/12/02/%E4%BD%8D%E5%9B%BE%E6%8E%92%E5%BA%8F/8394323_1303655564lhFb.jpg" alt="8394323_1303655564lhFb"></p>
<p>最后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。</p>
<p><strong>这样只需要开辟8个Bit（1Bytes）就可以记录每个数据并达到排序的目的。</strong></p>
<h2 id="算法实现（C-）"><a href="#算法实现（C-）" class="headerlink" title="算法实现（C++）"></a>算法实现（C++）</h2><p>示例中，位图法对不重复unsigned int 数的排序。</p>
<p>产生不重复unsigned int 数据请参考：<a target="_blank" rel="noopener" href="http://blog.csdn.net/lanzhihui_10086/article/details/50096265">产生数据</a></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;fstream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bitset&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;ctime&gt;</span></span></span><br><span class="line"> </span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"> </span><br><span class="line"><span class="keyword">const</span> <span class="keyword">unsigned</span> <span class="keyword">int</span> max_num=<span class="number">20000</span>;<span class="comment">//数字最大</span></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">unsigned</span> <span class="keyword">int</span> max_count=<span class="number">10000</span>;<span class="comment">//数据个数</span></span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	bitset&lt;max_num+1&gt; bit;</span><br><span class="line">	<span class="keyword">int</span> tmp=<span class="number">0</span>;</span><br><span class="line"> </span><br><span class="line">	<span class="comment">//以下读取磁盘文件中的数据</span></span><br><span class="line">	ifstream in_ran;</span><br><span class="line">	in_ran.<span class="built_in">open</span>(<span class="string">&quot;F:\\gz\\random.txt&quot;</span>,ios::in|ios::_Nocreate);</span><br><span class="line"> </span><br><span class="line">	<span class="keyword">if</span>(in_ran.<span class="built_in">fail</span>())</span><br><span class="line">	&#123;</span><br><span class="line">		cout&lt;&lt;<span class="string">&quot;打开文件失败!&quot;</span>&lt;&lt;endl;</span><br><span class="line">		<span class="built_in">exit</span>(<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line"> </span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;max_count;i++)</span><br><span class="line">	&#123;</span><br><span class="line">		in_ran&gt;&gt;tmp;    <span class="comment">//从文件中读取数据</span></span><br><span class="line">		bit.<span class="built_in">set</span>(tmp,<span class="number">1</span>);<span class="comment">//从磁盘文件读取100个整数，顺序存放在a数组中</span></span><br><span class="line">	&#125;</span><br><span class="line">	in_ran.<span class="built_in">close</span>();</span><br><span class="line"> </span><br><span class="line">	<span class="comment">//以下向磁盘文件写入数据--排序后的数据</span></span><br><span class="line">	ofstream out_sort;</span><br><span class="line">	out_sort.<span class="built_in">open</span>(<span class="string">&quot;F:\\gz\\random_sort.txt&quot;</span>,ios::out);</span><br><span class="line"> </span><br><span class="line">	<span class="keyword">if</span>(out_sort.<span class="built_in">fail</span>())</span><br><span class="line">	&#123;</span><br><span class="line">		cout&lt;&lt;<span class="string">&quot;打开文件失败!&quot;</span>&lt;&lt;endl;</span><br><span class="line">		<span class="built_in">exit</span>(<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line"> </span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;max_num;j++)<span class="comment">//输出排序后的随机数</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(bit[j]==<span class="number">1</span>)</span><br><span class="line">		&#123;</span><br><span class="line">			out_sort&lt;&lt;j&lt;&lt;<span class="string">&quot; &quot;</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	out_sort.<span class="built_in">close</span>();</span><br><span class="line"> </span><br><span class="line">	<span class="built_in">system</span>(<span class="string">&quot;pause&quot;</span>);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>与以往先将读取的数据储存在数组中，然后在进行排序相比，此排序方法没有中间数组作为传递，而且只须查询遍历一次数据即可得出排序后的结果。特别适用于无重复的整数排序。</p>
</div></article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">Author: </span><span class="post-copyright-info"><a href="mailto:undefined">LiYang</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">Link: </span><span class="post-copyright-info"><a href="http://example.com/2021/12/02/位图排序/">http://example.com/2021/12/02/位图排序/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">Copyright Notice: </span><span class="post-copyright-info">All articles in this blog are licensed under <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC BY-NC-SA 4.0</a> unless stating additionally.</span></div></div><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E7%AE%97%E6%B3%95%E8%89%BA%E6%9C%AF/">算法艺术</a></div><nav id="pagination"><div class="prev-post pull-left"><a href="/2021/12/07/C-%E4%B8%AD%E7%9A%84new-delete%E5%92%8Cmalloc-free/"><i class="fa fa-chevron-left">  </i><span>C++中的new/delete和malloc/free</span></a></div><div class="next-post pull-right"><a href="/2021/11/10/%E7%90%86%E8%A7%A3C-%E8%99%9A%E5%87%BD%E6%95%B0%E8%A1%A8/"><span>理解C++虚函数表</span><i class="fa fa-chevron-right"></i></a></div></nav></div></div><footer><div class="layout" id="footer"><div class="copyright">&copy;2013 - 2022 By LiYang</div><div class="framework-info"><span>Driven - </span><a target="_blank" rel="noopener" href="http://hexo.io"><span>Hexo</span></a><span class="footer-separator">|</span><span>Theme - </span><a target="_blank" rel="noopener" href="https://github.com/Molunerfinn/hexo-theme-melody"><span>Melody</span></a></div><div class="busuanzi"><script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><span id="busuanzi_container_page_pv"><i class="fa fa-file"></i><span id="busuanzi_value_page_pv"></span><span></span></span></div></div></footer><i class="fa fa-arrow-up" id="go-up" aria-hidden="true"></i><script src="https://cdn.jsdelivr.net/npm/animejs@latest/anime.min.js"></script><script src="https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js"></script><script src="https://cdn.jsdelivr.net/npm/velocity-animate@latest/velocity.min.js"></script><script src="https://cdn.jsdelivr.net/npm/velocity-ui-pack@latest/velocity.ui.min.js"></script><script src="/js/utils.js?version=1.9.0"></script><script src="/js/fancybox.js?version=1.9.0"></script><script src="/js/sidebar.js?version=1.9.0"></script><script src="/js/copy.js?version=1.9.0"></script><script src="/js/fireworks.js?version=1.9.0"></script><script src="/js/transition.js?version=1.9.0"></script><script src="/js/scroll.js?version=1.9.0"></script><script src="/js/head.js?version=1.9.0"></script><script>if(/Android|webOS|iPhone|iPod|iPad|BlackBerry/i.test(navigator.userAgent)) {
  $('#nav').addClass('is-mobile')
  $('footer').addClass('is-mobile')
  $('#top-container').addClass('is-mobile')
}</script></body></html>